#include <vector>
#include <iostream>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> S;
        stack<int> rS;
        vector<int> rst;

        for(int i = 0; i < asteroids.size(); ++i){
            if(asteroids[i] < 0){
                if(S.empty()){
                    rst.push_back(asteroids[i]);
                }
                else{
                    while(!S.empty()){
                        int bump = S.top() + asteroids[i];
                        if(bump == 0){
                            S.pop();
                            break;
                        }else if(bump > 0){
                            break;
                        }else{
                            S.pop();
                            if(S.empty()){
                                rst.push_back(asteroids[i]);
                            }
                        }
                    }
                }
            }else{
                S.push(asteroids[i]);
            }
        }

        
        while(!S.empty()){
            rS.push(S.top());
            S.pop();
        }

        while(!rS.empty()){
            rst.push_back(rS.top());
            rS.pop();
        }

        return rst;
    }
};